package com.dyz.otherAlgorithm;

import java.util.Arrays;

/**
 * @author: daiyizheng
 * @date: 2021/5/21 16:21
 * @description:
 */
public class LCS {

    public static void main(String[] args) {
        String text1 = new String("abcde");
        String text2 = new String("ace");
        int num = new LCS().longestCommonSubsequence(text1, text2);
        System.out.println(num);

    }

    public int longestCommonSubsequence(String text1, String text2){
        //求长度
        int row = text1.length();
        int col = text2.length();
        int[][] dp = new int[row+1][col+1];
        StringBuilder ans = new StringBuilder();
        for (int i=1;i<=row;i++){
            for(int j=1; j<=col;j++){
                char c1 = text1.charAt(i-1);//数组记录从1开始，字符串下标从0开始，所以需要-1；
                char c2 = text2.charAt(j-1);
                if(c1 == c2){
                    dp[i][j] = dp[i-1][j-1] +1;//当前字符相等时，在上对角的值的基础上+1；
                    ans.append(c1);
                }else {
                    //从左边和右边取最大值
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        System.out.println(ans.toString());
        return dp[row][col];
    }
}
